package com.mingweicai.intergration.sort;

public class QuickSort {

  public static void main(String args[]){
    int arr[] = new int[]{6,5,4,3,1};
    quickSort(arr,0, arr.length - 1);
    for(int i=0; i<arr.length; i++){
      System.out.print(arr[i] + " ");
    }
  }

  private static void quickSort(int arr[], int low, int high){
    if(low < high){
      int pivotkey = partition(arr, low, high);
      quickSort(arr, low, pivotkey - 1);
      quickSort(arr, pivotkey+1, high);
    }
  }

  private static int partition(int arr[], int low, int high){
    int pivotkey = arr[low];
    while(low<high){
      while(low<high && arr[high] >= pivotkey)
        high --;
      swap(arr,low,high);
      while(low<high && arr[low] <= pivotkey)
        low++;
      swap(arr,low,high);
    }
    return low;
  }

  private static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
